use crate::raw::{

    Allocator, Bucket, Global, RawDrain, RawExtractIf, RawIntoIter, RawIter, RawTable,

};

use crate::{Equivalent, TryReserveError};

use core::borrow::Borrow;

use core::fmt::{self, Debug};

use core::hash::{BuildHasher, Hash};

use core::iter::{FromIterator, FusedIterator};

use core::marker::PhantomData;

use core::mem;

use core::ops::Index;

/// Default hasher for `HashMap`.

#[cfg(feature = "ahash")]

pub type DefaultHashBuilder = core::hash::BuildHasherDefault<ahash::AHasher>;

/// Dummy default hasher for `HashMap`.

#[cfg(not(feature = "ahash"))]

pub enum DefaultHashBuilder {}

/// A hash map implemented with quadratic probing and SIMD lookup.

///

/// The default hashing algorithm is currently [`AHash`], though this is

/// subject to change at any point in the future. This hash function is very

/// fast for all types of keys, but this algorithm will typically *not* protect

/// against attacks such as HashDoS.

///

/// The hashing algorithm can be replaced on a per-`HashMap` basis using the

/// [`default`], [`with_hasher`], and [`with_capacity_and_hasher`] methods. Many

/// alternative algorithms are available on crates.io, such as the [`fnv`] crate.

///

/// It is required that the keys implement the [`Eq`] and [`Hash`] traits, although

/// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.

/// If you implement these yourself, it is important that the following

/// property holds:

///

/// ```text

/// k1 == k2 -> hash(k1) == hash(k2)

/// ```

///

/// In other words, if two keys are equal, their hashes must be equal.

///

/// It is a logic error for a key to be modified in such a way that the key's

/// hash, as determined by the [`Hash`] trait, or its equality, as determined by

/// the [`Eq`] trait, changes while it is in the map. This is normally only

/// possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.

///

/// It is also a logic error for the [`Hash`] implementation of a key to panic.

/// This is generally only possible if the trait is implemented manually. If a

/// panic does occur then the contents of the `HashMap` may become corrupted and

/// some items may be dropped from the table.

///

/// # Examples

///

/// ```

/// use hashbrown::HashMap;

///

/// // Type inference lets us omit an explicit type signature (which

/// // would be `HashMap<String, String>` in this example).

/// let mut book_reviews = HashMap::new();

///

/// // Review some books.

/// book_reviews.insert(

///     "Adventures of Huckleberry Finn".to_string(),

///     "My favorite book.".to_string(),

/// );

/// book_reviews.insert(

///     "Grimms' Fairy Tales".to_string(),

///     "Masterpiece.".to_string(),

/// );

/// book_reviews.insert(

///     "Pride and Prejudice".to_string(),

///     "Very enjoyable.".to_string(),

/// );

/// book_reviews.insert(

///     "The Adventures of Sherlock Holmes".to_string(),

///     "Eye lyked it alot.".to_string(),

/// );

///

/// // Check for a specific one.

/// // When collections store owned values (String), they can still be

/// // queried using references (&str).

/// if !book_reviews.contains_key("Les Misérables") {

///     println!("We've got {} reviews, but Les Misérables ain't one.",

///              book_reviews.len());

/// }

///

/// // oops, this review has a lot of spelling mistakes, let's delete it.

/// book_reviews.remove("The Adventures of Sherlock Holmes");

///

/// // Look up the values associated with some keys.

/// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];

/// for &book in &to_find {

///     match book_reviews.get(book) {

///         Some(review) => println!("{}: {}", book, review),

///         None => println!("{} is unreviewed.", book)

///     }

/// }

///

/// // Look up the value for a key (will panic if the key is not found).

/// println!("Review for Jane: {}", book_reviews["Pride and Prejudice"]);

///

/// // Iterate over everything.

/// for (book, review) in &book_reviews {

///     println!("{}: \"{}\"", book, review);

/// }

/// ```

///

/// `HashMap` also implements an [`Entry API`](#method.entry), which allows

/// for more complex methods of getting, setting, updating and removing keys and

/// their values:

///

/// ```

/// use hashbrown::HashMap;

///

/// // type inference lets us omit an explicit type signature (which

/// // would be `HashMap<&str, u8>` in this example).

/// let mut player_stats = HashMap::new();

///

/// fn random_stat_buff() -> u8 {

///     // could actually return some random value here - let's just return

///     // some fixed value for now

///     42

/// }

///

/// // insert a key only if it doesn't already exist

/// player_stats.entry("health").or_insert(100);

///

/// // insert a key using a function that provides a new value only if it

/// // doesn't already exist

/// player_stats.entry("defence").or_insert_with(random_stat_buff);

///

/// // update a key, guarding against the key possibly not being set

/// let stat = player_stats.entry("attack").or_insert(100);

/// *stat += random_stat_buff();

/// ```

///

/// The easiest way to use `HashMap` with a custom key type is to derive [`Eq`] and [`Hash`].

/// We must also derive [`PartialEq`].

///

/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html

/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html

/// [`PartialEq`]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html

/// [`RefCell`]: https://doc.rust-lang.org/std/cell/struct.RefCell.html

/// [`Cell`]: https://doc.rust-lang.org/std/cell/struct.Cell.html

/// [`default`]: #method.default

/// [`with_hasher`]: #method.with_hasher

/// [`with_capacity_and_hasher`]: #method.with_capacity_and_hasher

/// [`fnv`]: https://crates.io/crates/fnv

/// [`AHash`]: https://crates.io/crates/ahash

///

/// ```

/// use hashbrown::HashMap;

///

/// #[derive(Hash, Eq, PartialEq, Debug)]

/// struct Viking {

///     name: String,

///     country: String,

/// }

///

/// impl Viking {

///     /// Creates a new Viking.

///     fn new(name: &str, country: &str) -> Viking {

///         Viking { name: name.to_string(), country: country.to_string() }

///     }

/// }

///

/// // Use a HashMap to store the vikings' health points.

/// let mut vikings = HashMap::new();

///

/// vikings.insert(Viking::new("Einar", "Norway"), 25);

/// vikings.insert(Viking::new("Olaf", "Denmark"), 24);

/// vikings.insert(Viking::new("Harald", "Iceland"), 12);

///

/// // Use derived implementation to print the status of the vikings.

/// for (viking, health) in &vikings {

///     println!("{:?} has {} hp", viking, health);

/// }

/// ```

///

/// A `HashMap` with fixed list of elements can be initialized from an array:

///

/// ```

/// use hashbrown::HashMap;

///

/// let timber_resources: HashMap<&str, i32> = [("Norway", 100), ("Denmark", 50), ("Iceland", 10)]

///     .iter().cloned().collect();

/// // use the values stored in map

/// ```

pub struct HashMap<K, V, S = DefaultHashBuilder, A: Allocator = Global> {

    pub(crate) hash_builder: S,

    pub(crate) table: RawTable<(K, V), A>,

}

impl<K: Clone, V: Clone, S: Clone, A: Allocator + Clone> Clone for HashMap<K, V, S, A> {

    fn clone(&self) -> Self {

        HashMap {

            hash_builder: self.hash_builder.clone(),

            table: self.table.clone(),

        }

    }

    fn clone_from(&mut self, source: &Self) {

        self.table.clone_from(&source.table);

        // Update hash_builder only if we successfully cloned all elements.

        self.hash_builder.clone_from(&source.hash_builder);

    }

}

/// Ensures that a single closure type across uses of this which, in turn prevents multiple

/// instances of any functions like RawTable::reserve from being generated

#[cfg_attr(feature = "inline-more", inline)]

/// Ensures that a single closure type across uses of this which, in turn prevents multiple

/// instances of any functions like RawTable::reserve from being generated

#[cfg_attr(feature = "inline-more", inline)]

/// Ensures that a single closure type across uses of this which, in turn prevents multiple

/// instances of any functions like RawTable::reserve from being generated

#[cfg_attr(feature = "inline-more", inline)]

fn equivalent<Q, K>(k: &Q) -> impl Fn(&K) -> bool + '_

where

    Q: ?Sized + Equivalent<K>,

{

    move |x| k.equivalent(x)

}

#[cfg(not(feature = "nightly"))]

#[cfg_attr(feature = "inline-more", inline)]

    use core::hash::Hasher;

#[cfg(feature = "nightly")]

#[cfg_attr(feature = "inline-more", inline)]

pub(crate) fn make_hash<Q, S>(hash_builder: &S, val: &Q) -> u64

where

    Q: Hash + ?Sized,

    S: BuildHasher,

{

    hash_builder.hash_one(val)

}

#[cfg(feature = "ahash")]

impl<K, V> HashMap<K, V, DefaultHashBuilder> {

    /// Creates an empty `HashMap`.

    ///

    /// The hash map is initially created with a capacity of 0, so it will not allocate until it

    /// is first inserted into.

    ///

    /// # HashDoS resistance

    ///

    /// The `hash_builder` normally use a fixed key by default and that does

    /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].

    /// Users who require HashDoS resistance should explicitly use

    /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`]

    /// as the hasher when creating a [`HashMap`], for example with

    /// [`with_hasher`](HashMap::with_hasher) method.

    ///

    /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack

    /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    /// let mut map: HashMap<&str, i32> = HashMap::new();

    /// assert_eq!(map.len(), 0);

    /// assert_eq!(map.capacity(), 0);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn new() -> Self {

        Self::default()

    }

    /// Creates an empty `HashMap` with the specified capacity.

    ///

    /// The hash map will be able to hold at least `capacity` elements without

    /// reallocating. If `capacity` is 0, the hash map will not allocate.

    ///

    /// # HashDoS resistance

    ///

    /// The `hash_builder` normally use a fixed key by default and that does

    /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].

    /// Users who require HashDoS resistance should explicitly use

    /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`]

    /// as the hasher when creating a [`HashMap`], for example with

    /// [`with_capacity_and_hasher`](HashMap::with_capacity_and_hasher) method.

    ///

    /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack

    /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    /// let mut map: HashMap<&str, i32> = HashMap::with_capacity(10);

    /// assert_eq!(map.len(), 0);

    /// assert!(map.capacity() >= 10);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

}

#[cfg(feature = "ahash")]

impl<K, V, A: Allocator> HashMap<K, V, DefaultHashBuilder, A> {

    /// Creates an empty `HashMap` using the given allocator.

    ///

    /// The hash map is initially created with a capacity of 0, so it will not allocate until it

    /// is first inserted into.

    ///

    /// # HashDoS resistance

    ///

    /// The `hash_builder` normally use a fixed key by default and that does

    /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].

    /// Users who require HashDoS resistance should explicitly use

    /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`]

    /// as the hasher when creating a [`HashMap`], for example with

    /// [`with_hasher_in`](HashMap::with_hasher_in) method.

    ///

    /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack

    /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    /// use bumpalo::Bump;

    ///

    /// let bump = Bump::new();

    /// let mut map = HashMap::new_in(&bump);

    ///

    /// // The created HashMap holds none elements

    /// assert_eq!(map.len(), 0);

    ///

    /// // The created HashMap also doesn't allocate memory

    /// assert_eq!(map.capacity(), 0);

    ///

    /// // Now we insert element inside created HashMap

    /// map.insert("One", 1);

    /// // We can see that the HashMap holds 1 element

    /// assert_eq!(map.len(), 1);

    /// // And it also allocates some capacity

    /// assert!(map.capacity() > 1);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn new_in(alloc: A) -> Self {

        Self::with_hasher_in(DefaultHashBuilder::default(), alloc)

    }

    /// Creates an empty `HashMap` with the specified capacity using the given allocator.

    ///

    /// The hash map will be able to hold at least `capacity` elements without

    /// reallocating. If `capacity` is 0, the hash map will not allocate.

    ///

    /// # HashDoS resistance

    ///

    /// The `hash_builder` normally use a fixed key by default and that does

    /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].

    /// Users who require HashDoS resistance should explicitly use

    /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`]

    /// as the hasher when creating a [`HashMap`], for example with

    /// [`with_capacity_and_hasher_in`](HashMap::with_capacity_and_hasher_in) method.

    ///

    /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack

    /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    /// use bumpalo::Bump;

    ///

    /// let bump = Bump::new();

    /// let mut map = HashMap::with_capacity_in(5, &bump);

    ///

    /// // The created HashMap holds none elements

    /// assert_eq!(map.len(), 0);

    /// // But it can hold at least 5 elements without reallocating

    /// let empty_map_capacity = map.capacity();

    /// assert!(empty_map_capacity >= 5);

    ///

    /// // Now we insert some 5 elements inside created HashMap

    /// map.insert("One",   1);

    /// map.insert("Two",   2);

    /// map.insert("Three", 3);

    /// map.insert("Four",  4);

    /// map.insert("Five",  5);

    ///

    /// // We can see that the HashMap holds 5 elements

    /// assert_eq!(map.len(), 5);

    /// // But its capacity isn't changed

    /// assert_eq!(map.capacity(), empty_map_capacity)

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {

        Self::with_capacity_and_hasher_in(capacity, DefaultHashBuilder::default(), alloc)

    }

}

impl<K, V, S> HashMap<K, V, S> {

    /// Creates an empty `HashMap` which will use the given hash builder to hash

    /// keys.

    ///

    /// The hash map is initially created with a capacity of 0, so it will not

    /// allocate until it is first inserted into.

    ///

    /// # HashDoS resistance

    ///

    /// The `hash_builder` normally use a fixed key by default and that does

    /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].

    /// Users who require HashDoS resistance should explicitly use

    /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`]

    /// as the hasher when creating a [`HashMap`].

    ///

    /// The `hash_builder` passed should implement the [`BuildHasher`] trait for

    /// the HashMap to be useful, see its documentation for details.

    ///

    /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack

    /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html

    /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    /// use hashbrown::hash_map::DefaultHashBuilder;

    ///

    /// let s = DefaultHashBuilder::default();

    /// let mut map = HashMap::with_hasher(s);

    /// assert_eq!(map.len(), 0);

    /// assert_eq!(map.capacity(), 0);

    ///

    /// map.insert(1, 2);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub const fn with_hasher(hash_builder: S) -> Self {

        Self {

            hash_builder,

            table: RawTable::new(),

        }

    }

    /// Creates an empty `HashMap` with the specified capacity, using `hash_builder`

    /// to hash the keys.

    ///

    /// The hash map will be able to hold at least `capacity` elements without

    /// reallocating. If `capacity` is 0, the hash map will not allocate.

    ///

    /// # HashDoS resistance

    ///

    /// The `hash_builder` normally use a fixed key by default and that does

    /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].

    /// Users who require HashDoS resistance should explicitly use

    /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`]

    /// as the hasher when creating a [`HashMap`].

    ///

    /// The `hash_builder` passed should implement the [`BuildHasher`] trait for

    /// the HashMap to be useful, see its documentation for details.

    ///

    /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack

    /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html

    /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    /// use hashbrown::hash_map::DefaultHashBuilder;

    ///

    /// let s = DefaultHashBuilder::default();

    /// let mut map = HashMap::with_capacity_and_hasher(10, s);

    /// assert_eq!(map.len(), 0);

    /// assert!(map.capacity() >= 10);

    ///

    /// map.insert(1, 2);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

}

impl<K, V, S, A: Allocator> HashMap<K, V, S, A> {

    /// Returns a reference to the underlying allocator.

    #[inline]

    pub fn allocator(&self) -> &A {

        self.table.allocator()

    }

    /// Creates an empty `HashMap` which will use the given hash builder to hash

    /// keys. It will be allocated with the given allocator.

    ///

    /// The hash map is initially created with a capacity of 0, so it will not allocate until it

    /// is first inserted into.

    ///

    /// # HashDoS resistance

    ///

    /// The `hash_builder` normally use a fixed key by default and that does

    /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].

    /// Users who require HashDoS resistance should explicitly use

    /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`]

    /// as the hasher when creating a [`HashMap`].

    ///

    /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack

    /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    /// use hashbrown::hash_map::DefaultHashBuilder;

    ///

    /// let s = DefaultHashBuilder::default();

    /// let mut map = HashMap::with_hasher(s);

    /// map.insert(1, 2);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    /// Creates an empty `HashMap` with the specified capacity, using `hash_builder`

    /// to hash the keys. It will be allocated with the given allocator.

    ///

    /// The hash map will be able to hold at least `capacity` elements without

    /// reallocating. If `capacity` is 0, the hash map will not allocate.

    ///

    /// # HashDoS resistance

    ///

    /// The `hash_builder` normally use a fixed key by default and that does

    /// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].

    /// Users who require HashDoS resistance should explicitly use

    /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`]

    /// as the hasher when creating a [`HashMap`].

    ///

    /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack

    /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    /// use hashbrown::hash_map::DefaultHashBuilder;

    ///

    /// let s = DefaultHashBuilder::default();

    /// let mut map = HashMap::with_capacity_and_hasher(10, s);

    /// map.insert(1, 2);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn with_capacity_and_hasher_in(capacity: usize, hash_builder: S, alloc: A) -> Self {

        Self {

            hash_builder,

            table: RawTable::with_capacity_in(capacity, alloc),

        }

    }

    /// Returns a reference to the map's [`BuildHasher`].

    ///

    /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    /// use hashbrown::hash_map::DefaultHashBuilder;

    ///

    /// let hasher = DefaultHashBuilder::default();

    /// let map: HashMap<i32, i32> = HashMap::with_hasher(hasher);

    /// let hasher: &DefaultHashBuilder = map.hasher();

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn hasher(&self) -> &S {

        &self.hash_builder

    }

    /// Returns the number of elements the map can hold without reallocating.

    ///

    /// This number is a lower bound; the `HashMap<K, V>` might be able to hold

    /// more, but is guaranteed to be able to hold at least this many.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    /// let map: HashMap<i32, i32> = HashMap::with_capacity(100);

    /// assert_eq!(map.len(), 0);

    /// assert!(map.capacity() >= 100);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn capacity(&self) -> usize {

        self.table.capacity()

    }

    /// An iterator visiting all keys in arbitrary order.

    /// The iterator element type is `&'a K`.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut map = HashMap::new();

    /// map.insert("a", 1);

    /// map.insert("b", 2);

    /// map.insert("c", 3);

    /// assert_eq!(map.len(), 3);

    /// let mut vec: Vec<&str> = Vec::new();

    ///

    /// for key in map.keys() {

    ///     println!("{}", key);

    ///     vec.push(*key);

    /// }

    ///

    /// // The `Keys` iterator produces keys in arbitrary order, so the

    /// // keys must be sorted to test them against a sorted array.

    /// vec.sort_unstable();

    /// assert_eq!(vec, ["a", "b", "c"]);

    ///

    /// assert_eq!(map.len(), 3);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn keys(&self) -> Keys<'_, K, V> {

        Keys { inner: self.iter() }

    }

    /// An iterator visiting all values in arbitrary order.

    /// The iterator element type is `&'a V`.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut map = HashMap::new();

    /// map.insert("a", 1);

    /// map.insert("b", 2);

    /// map.insert("c", 3);

    /// assert_eq!(map.len(), 3);

    /// let mut vec: Vec<i32> = Vec::new();

    ///

    /// for val in map.values() {

    ///     println!("{}", val);

    ///     vec.push(*val);

    /// }

    ///

    /// // The `Values` iterator produces values in arbitrary order, so the

    /// // values must be sorted to test them against a sorted array.

    /// vec.sort_unstable();

    /// assert_eq!(vec, [1, 2, 3]);

    ///

    /// assert_eq!(map.len(), 3);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn values(&self) -> Values<'_, K, V> {

        Values { inner: self.iter() }

    }

    /// An iterator visiting all values mutably in arbitrary order.

    /// The iterator element type is `&'a mut V`.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut map = HashMap::new();

    ///

    /// map.insert("a", 1);

    /// map.insert("b", 2);

    /// map.insert("c", 3);

    ///

    /// for val in map.values_mut() {

    ///     *val = *val + 10;

    /// }

    ///

    /// assert_eq!(map.len(), 3);

    /// let mut vec: Vec<i32> = Vec::new();

    ///

    /// for val in map.values() {

    ///     println!("{}", val);

    ///     vec.push(*val);

    /// }

    ///

    /// // The `Values` iterator produces values in arbitrary order, so the

    /// // values must be sorted to test them against a sorted array.

    /// vec.sort_unstable();

    /// assert_eq!(vec, [11, 12, 13]);

    ///

    /// assert_eq!(map.len(), 3);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {

        ValuesMut {

            inner: self.iter_mut(),

        }

    }

    /// An iterator visiting all key-value pairs in arbitrary order.

    /// The iterator element type is `(&'a K, &'a V)`.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut map = HashMap::new();

    /// map.insert("a", 1);

    /// map.insert("b", 2);

    /// map.insert("c", 3);

    /// assert_eq!(map.len(), 3);

    /// let mut vec: Vec<(&str, i32)> = Vec::new();

    ///

    /// for (key, val) in map.iter() {

    ///     println!("key: {} val: {}", key, val);

    ///     vec.push((*key, *val));

    /// }

    ///

    /// // The `Iter` iterator produces items in arbitrary order, so the

    /// // items must be sorted to test them against a sorted array.

    /// vec.sort_unstable();

    /// assert_eq!(vec, [("a", 1), ("b", 2), ("c", 3)]);

    ///

    /// assert_eq!(map.len(), 3);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn iter(&self) -> Iter<'_, K, V> {

        // Here we tie the lifetime of self to the iter.

        unsafe {

            Iter {

                inner: self.table.iter(),

                marker: PhantomData,

            }

        }

    }

    /// An iterator visiting all key-value pairs in arbitrary order,

    /// with mutable references to the values.

    /// The iterator element type is `(&'a K, &'a mut V)`.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut map = HashMap::new();

    /// map.insert("a", 1);

    /// map.insert("b", 2);

    /// map.insert("c", 3);

    ///

    /// // Update all values

    /// for (_, val) in map.iter_mut() {

    ///     *val *= 2;

    /// }

    ///

    /// assert_eq!(map.len(), 3);

    /// let mut vec: Vec<(&str, i32)> = Vec::new();

    ///

    /// for (key, val) in &map {

    ///     println!("key: {} val: {}", key, val);

    ///     vec.push((*key, *val));

    /// }

    ///

    /// // The `Iter` iterator produces items in arbitrary order, so the

    /// // items must be sorted to test them against a sorted array.

    /// vec.sort_unstable();

    /// assert_eq!(vec, [("a", 2), ("b", 4), ("c", 6)]);

    ///

    /// assert_eq!(map.len(), 3);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {

        // Here we tie the lifetime of self to the iter.

        unsafe {

            IterMut {

                inner: self.table.iter(),

                marker: PhantomData,

            }

        }

    }

    #[cfg(test)]

    #[cfg_attr(feature = "inline-more", inline)]

    fn raw_capacity(&self) -> usize {

        self.table.buckets()

    }

    /// Returns the number of elements in the map.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut a = HashMap::new();

    /// assert_eq!(a.len(), 0);

    /// a.insert(1, "a");

    /// assert_eq!(a.len(), 1);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    /// Returns `true` if the map contains no elements.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut a = HashMap::new();

    /// assert!(a.is_empty());

    /// a.insert(1, "a");

    /// assert!(!a.is_empty());

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn is_empty(&self) -> bool {

        self.len() == 0

    }

    /// Clears the map, returning all key-value pairs as an iterator. Keeps the

    /// allocated memory for reuse.

    ///

    /// If the returned iterator is dropped before being fully consumed, it

    /// drops the remaining key-value pairs. The returned iterator keeps a

    /// mutable borrow on the vector to optimize its implementation.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut a = HashMap::new();

    /// a.insert(1, "a");

    /// a.insert(2, "b");

    /// let capacity_before_drain = a.capacity();

    ///

    /// for (k, v) in a.drain().take(1) {

    ///     assert!(k == 1 || k == 2);

    ///     assert!(v == "a" || v == "b");

    /// }

    ///

    /// // As we can see, the map is empty and contains no element.

    /// assert!(a.is_empty() && a.len() == 0);

    /// // But map capacity is equal to old one.

    /// assert_eq!(a.capacity(), capacity_before_drain);

    ///

    /// let mut a = HashMap::new();

    /// a.insert(1, "a");

    /// a.insert(2, "b");

    ///

    /// {   // Iterator is dropped without being consumed.

    ///     let d = a.drain();

    /// }

    ///

    /// // But the map is empty even if we do not use Drain iterator.

    /// assert!(a.is_empty());

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    /// Retains only the elements specified by the predicate. Keeps the

    /// allocated memory for reuse.

    ///

    /// In other words, remove all pairs `(k, v)` such that `f(&k, &mut v)` returns `false`.

    /// The elements are visited in unsorted (and unspecified) order.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut map: HashMap<i32, i32> = (0..8).map(|x|(x, x*10)).collect();

    /// assert_eq!(map.len(), 8);

    ///

    /// map.retain(|&k, _| k % 2 == 0);

    ///

    /// // We can see, that the number of elements inside map is changed.

    /// assert_eq!(map.len(), 4);

    ///

    /// let mut vec: Vec<(i32, i32)> = map.iter().map(|(&k, &v)| (k, v)).collect();

    /// vec.sort_unstable();

    /// assert_eq!(vec, [(0, 0), (2, 20), (4, 40), (6, 60)]);

    /// ```

    pub fn retain<F>(&mut self, mut f: F)

    where

        F: FnMut(&K, &mut V) -> bool,

    {

        // Here we only use `iter` as a temporary, preventing use-after-free

        unsafe {

            for item in self.table.iter() {

                let &mut (ref key, ref mut value) = item.as_mut();

                if !f(key, value) {

                    self.table.erase(item);

                }

            }

        }

    }

    /// Drains elements which are true under the given predicate,

    /// and returns an iterator over the removed items.

    ///

    /// In other words, move all pairs `(k, v)` such that `f(&k, &mut v)` returns `true` out

    /// into another iterator.

    ///

    /// Note that `extract_if` lets you mutate every value in the filter closure, regardless of

    /// whether you choose to keep or remove it.

    ///

    /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating

    /// or the iteration short-circuits, then the remaining elements will be retained.

    /// Use [`retain()`] with a negated predicate if you do not need the returned iterator.

    ///

    /// Keeps the allocated memory for reuse.

    ///

    /// [`retain()`]: HashMap::retain

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x)).collect();

    ///

    /// let drained: HashMap<i32, i32> = map.extract_if(|k, _v| k % 2 == 0).collect();

    ///

    /// let mut evens = drained.keys().cloned().collect::<Vec<_>>();

    /// let mut odds = map.keys().cloned().collect::<Vec<_>>();

    /// evens.sort();

    /// odds.sort();

    ///

    /// assert_eq!(evens, vec![0, 2, 4, 6]);

    /// assert_eq!(odds, vec![1, 3, 5, 7]);

    ///

    /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x)).collect();

    ///

    /// {   // Iterator is dropped without being consumed.

    ///     let d = map.extract_if(|k, _v| k % 2 != 0);

    /// }

    ///

    /// // ExtractIf was not exhausted, therefore no elements were drained.

    /// assert_eq!(map.len(), 8);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn extract_if<F>(&mut self, f: F) -> ExtractIf<'_, K, V, F, A>

    where

        F: FnMut(&K, &mut V) -> bool,

    {

        ExtractIf {

            f,

            inner: RawExtractIf {

                iter: unsafe { self.table.iter() },

                table: &mut self.table,

            },

        }

    }

    /// Clears the map, removing all key-value pairs. Keeps the allocated memory

    /// for reuse.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut a = HashMap::new();

    /// a.insert(1, "a");

    /// let capacity_before_clear = a.capacity();

    ///

    /// a.clear();

    ///

    /// // Map is empty.

    /// assert!(a.is_empty());

    /// // But map capacity is equal to old one.

    /// assert_eq!(a.capacity(), capacity_before_clear);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn clear(&mut self) {

        self.table.clear();

    }

    /// Creates a consuming iterator visiting all the keys in arbitrary order.

    /// The map cannot be used after calling this.

    /// The iterator element type is `K`.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut map = HashMap::new();

    /// map.insert("a", 1);

    /// map.insert("b", 2);

    /// map.insert("c", 3);

    ///

    /// let mut vec: Vec<&str> = map.into_keys().collect();

    ///

    /// // The `IntoKeys` iterator produces keys in arbitrary order, so the

    /// // keys must be sorted to test them against a sorted array.

    /// vec.sort_unstable();

    /// assert_eq!(vec, ["a", "b", "c"]);

    /// ```

    #[inline]

    pub fn into_keys(self) -> IntoKeys<K, V, A> {

        IntoKeys {

            inner: self.into_iter(),

        }

    }

    /// Creates a consuming iterator visiting all the values in arbitrary order.

    /// The map cannot be used after calling this.

    /// The iterator element type is `V`.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut map = HashMap::new();

    /// map.insert("a", 1);

    /// map.insert("b", 2);

    /// map.insert("c", 3);

    ///

    /// let mut vec: Vec<i32> = map.into_values().collect();

    ///

    /// // The `IntoValues` iterator produces values in arbitrary order, so

    /// // the values must be sorted to test them against a sorted array.

    /// vec.sort_unstable();

    /// assert_eq!(vec, [1, 2, 3]);

    /// ```

    #[inline]

    pub fn into_values(self) -> IntoValues<K, V, A> {

        IntoValues {

            inner: self.into_iter(),

        }

    }

}

impl<K, V, S, A> HashMap<K, V, S, A>

where

    K: Eq + Hash,

    S: BuildHasher,

    A: Allocator,

{

    /// Reserves capacity for at least `additional` more elements to be inserted

    /// in the `HashMap`. The collection may reserve more space to avoid

    /// frequent reallocations.

    ///

    /// # Panics

    ///

    /// Panics if the new capacity exceeds [`isize::MAX`] bytes and [`abort`] the program

    /// in case of allocation error. Use [`try_reserve`](HashMap::try_reserve) instead

    /// if you want to handle memory allocation failure.

    ///

    /// [`isize::MAX`]: https://doc.rust-lang.org/std/primitive.isize.html

    /// [`abort`]: https://doc.rust-lang.org/alloc/alloc/fn.handle_alloc_error.html

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    /// let mut map: HashMap<&str, i32> = HashMap::new();

    /// // Map is empty and doesn't allocate memory

    /// assert_eq!(map.capacity(), 0);

    ///

    /// map.reserve(10);

    ///

    /// // And now map can hold at least 10 elements

    /// assert!(map.capacity() >= 10);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn reserve(&mut self, additional: usize) {

        self.table

            .reserve(additional, make_hasher::<_, V, S>(&self.hash_builder));

    }

    /// Tries to reserve capacity for at least `additional` more elements to be inserted

    /// in the given `HashMap<K,V>`. The collection may reserve more space to avoid

    /// frequent reallocations.

    ///

    /// # Errors

    ///

    /// If the capacity overflows, or the allocator reports a failure, then an error

    /// is returned.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut map: HashMap<&str, isize> = HashMap::new();

    /// // Map is empty and doesn't allocate memory

    /// assert_eq!(map.capacity(), 0);

    ///

    /// map.try_reserve(10).expect("why is the test harness OOMing on 10 bytes?");

    ///

    /// // And now map can hold at least 10 elements

    /// assert!(map.capacity() >= 10);

    /// ```

    /// If the capacity overflows, or the allocator reports a failure, then an error

    /// is returned:

    /// ```

    /// # fn test() {

    /// use hashbrown::HashMap;

    /// use hashbrown::TryReserveError;

    /// let mut map: HashMap<i32, i32> = HashMap::new();

    ///

    /// match map.try_reserve(usize::MAX) {

    ///     Err(error) => match error {

    ///         TryReserveError::CapacityOverflow => {}

    ///         _ => panic!("TryReserveError::AllocError ?"),

    ///     },

    ///     _ => panic!(),

    /// }

    /// # }

    /// # fn main() {

    /// #     #[cfg(not(miri))]

    /// #     test()

    /// # }

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {

        self.table

            .try_reserve(additional, make_hasher::<_, V, S>(&self.hash_builder))

    }

    /// Shrinks the capacity of the map as much as possible. It will drop

    /// down as much as possible while maintaining the internal rules

    /// and possibly leaving some space in accordance with the resize policy.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);

    /// map.insert(1, 2);

    /// map.insert(3, 4);

    /// assert!(map.capacity() >= 100);

    /// map.shrink_to_fit();

    /// assert!(map.capacity() >= 2);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn shrink_to_fit(&mut self) {

        self.table

            .shrink_to(0, make_hasher::<_, V, S>(&self.hash_builder));

    }

    /// Shrinks the capacity of the map with a lower limit. It will drop

    /// down no lower than the supplied limit while maintaining the internal rules

    /// and possibly leaving some space in accordance with the resize policy.

    ///

    /// This function does nothing if the current capacity is smaller than the

    /// supplied minimum capacity.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);

    /// map.insert(1, 2);

    /// map.insert(3, 4);

    /// assert!(map.capacity() >= 100);

    /// map.shrink_to(10);

    /// assert!(map.capacity() >= 10);

    /// map.shrink_to(0);

    /// assert!(map.capacity() >= 2);

    /// map.shrink_to(10);

    /// assert!(map.capacity() >= 2);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn shrink_to(&mut self, min_capacity: usize) {

        self.table

            .shrink_to(min_capacity, make_hasher::<_, V, S>(&self.hash_builder));

    }

    /// Gets the given key's corresponding entry in the map for in-place manipulation.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut letters = HashMap::new();

    ///

    /// for ch in "a short treatise on fungi".chars() {

    ///     let counter = letters.entry(ch).or_insert(0);

    ///     *counter += 1;

    /// }

    ///

    /// assert_eq!(letters[&'s'], 2);

    /// assert_eq!(letters[&'t'], 3);

    /// assert_eq!(letters[&'u'], 1);

    /// assert_eq!(letters.get(&'y'), None);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn entry(&mut self, key: K) -> Entry<'_, K, V, S, A> {

        let hash = make_hash::<K, S>(&self.hash_builder, &key);

        if let Some(elem) = self.table.find(hash, equivalent_key(&key)) {

            Entry::Occupied(OccupiedEntry {

                hash,

                key: Some(key),

                elem,

                table: self,

            })

        } else {

            Entry::Vacant(VacantEntry {

                hash,

                key,

                table: self,

            })

        }

    }

    /// Gets the given key's corresponding entry by reference in the map for in-place manipulation.

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut words: HashMap<String, usize> = HashMap::new();

    /// let source = ["poneyland", "horseyland", "poneyland", "poneyland"];

    /// for (i, &s) in source.iter().enumerate() {

    ///     let counter = words.entry_ref(s).or_insert(0);

    ///     *counter += 1;

    /// }

    ///

    /// assert_eq!(words["poneyland"], 3);

    /// assert_eq!(words["horseyland"], 1);

    /// ```

    #[cfg_attr(feature = "inline-more", inline)]

    pub fn entry_ref<'a, 'b, Q: ?Sized>(&'a mut self, key: &'b Q) -> EntryRef<'a, 'b, K, Q, V, S, A>

    where

        Q: Hash + Equivalent<K>,

    {

        let hash = make_hash::<Q, S>(&self.hash_builder, key);

        if let Some(elem) = self.table.find(hash, equivalent_key(key)) {

            EntryRef::Occupied(OccupiedEntryRef {

                hash,

                key: Some(KeyOrRef::Borrowed(key)),

                elem,

                table: self,

            })

        } else {

            EntryRef::Vacant(VacantEntryRef {

                hash,

                key: KeyOrRef::Borrowed(key),

                table: self,

            })

        }

    }

    /// Returns a reference to the value corresponding to the key.

    ///

    /// The key may be any borrowed form of the map's key type, but

    /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for

    /// the key type.

    ///

    /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html

    /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///

    /// let mut map = HashMap::new();

    /// map.insert(1, "a");

    /// assert_eq!(map.get(&1), Some(&"a"));

    /// assert_eq!(map.get(&2), None);

    /// ```

    #[inline]

    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>

    where

        Q: Hash + Equivalent<K>,

    {

        // Avoid `Option::map` because it bloats LLVM IR.

        match self.get_inner(k) {

            Some((_, v)) => Some(v),

            None => None,

        }

    }

    /// Returns the key-value pair corresponding to the supplied key.

    ///

    /// The supplied key may be any borrowed form of the map's key type, but

    /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for

    /// the key type.

    ///

    /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html

    /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html

    ///

    /// # Examples

    ///

    /// ```

    /// use hashbrown::HashMap;

    ///